#include"tool.h"

void sort(int *a,int s,int e)
{
    if(s>=e)
    return ;
    int i,p,t;
    /**a[0:s-1] sorted a[s:e]unsorted*/
    sort(a,s,e-1);
    /**a[0:e-1] sorted
    insert a[e] at right place
    */
    for(i=e-1;i>=s;i--)
        if(a[i]<=a[e])
            break;

    p=i+1;
   // printf("a[i]=%d p=%d i=%d\n",a[i],p,i);
    t=a[e];
    for(i=e-1;i>=p;i--)
        a[i+1]=a[i];
    a[p]=t;

}
int main()
{
    int a[]= {1,7,4,5,3,2,8,9,0,8,8,8,9};
    int n=sizeof(a)/sizeof(a[0]);
    print(a,n);
    sort(a,0,n-1);
    print(a,n);

    return 0;
}
